package 单调栈;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class 含特定字母的最小子序列 {

    public String smallestSubsequence(String s, int k, char letter, int repetition) {
        Stack<Character> tempS=new Stack<>();
        char[] charS=s.toCharArray();
        int len=s.length();
        int[] preLe=new int[len+1];
        //统计当前字符后面letter的数量
        for(int i=len-1;i>=0;i--){
            preLe[i]=preLe[i+1] + (charS[i]==letter?1:0);
        }
        // 放入单调栈中letter的数量
        int curLe=0;
        for(int i=0;i<len;i++){
            //1,判断是否为null，2,当前这个字符是不是更优，3,之后的字符可以组成k个长度
            while(!tempS.isEmpty() && tempS.peek()>charS[i] && ( tempS.size()-1+len-i>=k ) ){
                int tempL=curLe;
                if(tempS.peek()==letter){
                    tempL--;
                }
                //4，letter字符是否不够   5，是否没有位置添加letter字符
                if(tempL+preLe[i]<repetition) {
                    break;
                }
                tempS.pop();
                curLe=tempL;
            }
            //长度没满并且能放非关键字符或者此时放关键字符
            if(tempS.size()<k && ( charS[i]==letter || k-tempS.size()>repetition-curLe ) ){
                if(charS[i]==letter){
                    curLe++;
                }
                tempS.push(charS[i]);
            }
        }
        StringBuffer sb = new StringBuffer();
        while(!tempS.isEmpty()){
            sb.append(tempS.pop());
        }
        String res=sb.reverse().toString();
        return res;
    }
    @Test
    public void test(){
        char c = 'a';
    }
}
